题解 SP8001@洛谷 | FIBOSUM@SPOJ 【FIBOSUM - Fibonacci Sum】

我也不知道我怎么找到的这题，但是既然 AC 了，就来写一篇题解。

题意简述：共 $T$ 组询问，每次读入两个数 $n,m$，输出 $\displaystyle\sum_{i=n}^ma_i\mod (10^9+7)$ 的值，其中 $a_i$ 为斐波那契数。

由于洛谷爬的时候漏掉了数据范围，可以到原题目中查看：$T\le 10^3,0 \le n\le m\le 10^9$，可以看到暴力求出所有斐波那契数的前缀和后求解显然会超时，容易想到矩阵加速。

我们使用矩阵维护第 $i$ 项、第 $i+1$ 项的值及前 $i$ 项的和，下面考虑构造转移矩阵。

根据斐波那契数列的定义，我们知道：

$\begin{cases}a_{i+1}=&a_{i+1}\\a_{i+2}=&a_{i}+a_{i+1}\\s_{i+1}=&s_i+a_{i+1}\end{cases}$

经过一些简单变换即可得到转移矩阵：

$\begin{bmatrix}a_i&a_{i+1}&s_i\end{bmatrix}\times\begin{bmatrix}0&1&0\\1&1&1\\0&0&1\end{bmatrix}=\begin{bmatrix}a_{i+1}&a_{i+2}&s_{i+1}\end{bmatrix}$

此时，我们可以通过类似于题目矩阵加速的方式利用矩阵快速幂在 $\log$ 时间内求出对于一个整数 $k$ 的 $s_k$ 的值。我们要求的答案即为 $s_m-s_{n-1}\mod (10^9+7)$。

代码：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;

ll T, n, m; 

struct Matrix {
	ll id[4][4];
	Matrix() {}
	Matrix(int x, int y, int z) {id[1][1]=x;id[1][2]=y;id[1][3]=z;} 
	~Matrix() {}
	void clear() {memset(id, 0, sizeof(id));}
	void init(ll k) {clear(); for(ll i=1;i<=k;i++) id[i][i] = 1;}
}a, b;

Matrix operator * (const Matrix &a, const Matrix &b) {
	Matrix c;
	c.clear();
	for(ll i=1;i<=3;i++)
		for(ll j=1;j<=3;j++)
			for(ll k=1;k<=3;k++)
				c.id[i][j] = (c.id[i][j] + a.id[i][k] * b.id[k][j] % mod) % mod;
	return c;
}

Matrix operator ^ (Matrix &a, ll k) {
	Matrix res;
	res.init(3);
	for(;k;k>>=1,a=a*a) if(k&1) res = res * a;
	return res;
}

Matrix calc(ll k) {
	if(k <= 0) return Matrix(0, 0, 0);
	if(k == 1) return Matrix(0, 1, 1);
	if(k == 2) return Matrix(1, 1, 2);
	a.clear(); b.clear();
	a.id[1][1] = a.id[1][2] = a.id[1][3] = 1;
	b.id[1][2] = b.id[2][1] = b.id[2][2] = b.id[2][3] = b.id[3][3] = 1;
	a = a * (b ^ (k - 1));
	return a;
}

int main() {
	scanf("%lld", &T);
	while(T--) {
		scanf("%lld%lld", &n, &m);
		printf("%lld\n", (calc(m).id[1][3]%mod-calc(n-1).id[1][3]%mod+mod)%mod);
	}
	return 0;
}